4858. Упорядоченные числа

У Миши развитое эстетическое чувство. Он считает, что не все числа одинаково упорядоченные. Когда ему грустно, он начинает придумывать числа и приводить их в порядок.

Миша очень любит рассматривать сумму цифр числа. Для того чтобы привести в порядок число a, он сначала записывает само число. Потом он пишет сумму цифр этого числа. Затем сумму цифр суммы цифр и так далее, до тех пор, пока очередное число не станет однозначным. Он считает, что результатом приведения в порядок числа a является сумма всех выписанных чисел, включая само число a.

Миша настолько любит этот процесс, что он даже заменяет ему счет овец, когда долго не получается заснуть. Он помнит, что вчера ночью, когда он в уме привел в порядок число a, у него получилось число b. Но вот беда – он не помнит, какое именно он взял число a! Помогите ему в отыскании этого числа.

Вход. Одно целое число b (1 ≤ b ≤ 10⁹).

Выход. Если существует такое число a, что после приведения его в порядок, получается b, то выведите любое такое число. Если же Миша где-то ошибся в расчетах и такого числа не существует, то выведите -1.

Пример входа 1	Пример выхода 1
42	29
Пример входа 2	Пример выхода 2
20	-1

РЕШЕНИЕ

математика

Анализ алгоритма

Пусть a = 999999999. Сумма его цифр равна a₁ = 81, сумма цифр числа a₁ равна a₂ = 9. Выписанными будут числа 999999999, 81, 9, их сумма равна 1000000089. Поскольку b ≤ 10⁹, то искомое значение a будет например не более, чем на 150 меньше числа b. Число a можно найти, перебрав все возможные значения из интервала [b – 150; b].

Реализация алгоритма

Вычисление суммы цифр числа.

int sum(int x)

{

if (x < 10) return x;

return sum(x / 10) + x % 10;

}

Приведение в порядок числа x. Вычисление суммы всех выписанных чисел.

int f(int x)

{

int res = x;

while (x > 9)

{

x = sum(x);

res += x;

}

return res;

}

Читаем входное значение n.

scanf("%d", &n);

На интервале [n – 150; n] в убывающем порядке ищем такое i, что сумма всех выписанных чисел при приведении в порядок числа i равна n.

for (i = n; i > n - 150; i--)

if (f(i) == n) break;

Выводим ответ. Если i = n – 150, то ответ не найден.

if (i == n - 150) printf("-1\n");

else printf("%d\n", i);